﻿//https://leetcode.cn/problems/M1oyTv/

class Solution {
public:
    string minWindow(string s, string t)
    {
        if (s.size() < t.size())
            return "";
        int hash1[128] = { 0 };
        int hash2[128] = { 0 };
        for (auto e : t)
        {
            hash1[e]++;
        }

        int left = 0, right = 0;
        int n = s.size(), m = t.size();
        int ret = 0x3f3f3f, len = 0;
        int begin = -1;
        int count = 0;
        while (right < n)
        {
            //进窗口
            if (++hash2[s[right]] <= hash1[s[right]])
            {
                count++;
            }
            //判断条件
            while (count == m)
            {
                //更新结果
                len = right - left + 1;
                if (len < ret)
                {
                    ret = len;
                    begin = left;
                }
                //出窗口
                if (--hash2[s[left]] < hash1[s[left]])
                {
                    count--;
                }
                left++;
            }
            right++;
        }

        return begin < 0 ? "" : s.substr(begin, ret);

    }
};
